package com.adee.algorithm.test.test20230418;

import java.util.Stack;

public class BSTTreeImpl {
    BSTNode root;

    public static void main(String[] args) {
        BSTTreeImpl tree = createTree();
        System.out.println(tree.get(0));
        System.out.println(tree.get(1));
        System.out.println(tree.get(2));
        System.out.println(tree.get(3));
        System.out.println(tree.get(4));
        System.out.println(tree.get(5));
        System.out.println(tree.get(6));
        System.out.println(tree.get(7));
        System.out.println(tree.get(8));

        System.out.println(tree.min());
        System.out.println(tree.max());

        tree.printTree();
        tree.put(3, "n3=");
        tree.printTree();
        tree.put(20, "n20");
        tree.printTree();

        System.out.println(tree.predecessor(1));
        System.out.println(tree.predecessor(2));
        System.out.println(tree.predecessor(3));
        System.out.println(tree.predecessor(4));
        System.out.println(tree.predecessor(5));
        System.out.println(tree.predecessor(6));
        System.out.println(tree.predecessor(7));
        System.out.println(tree.predecessor(8));

        System.out.println("====================");

        System.out.println(tree.postdecessor(1));
        System.out.println(tree.postdecessor(2));
        System.out.println(tree.postdecessor(3));
        System.out.println(tree.postdecessor(4));
        System.out.println(tree.postdecessor(5));
        System.out.println(tree.postdecessor(6));
        System.out.println(tree.postdecessor(7));
        System.out.println(tree.postdecessor(8));

        tree.isValid();
        createTree2().isValid();

        System.out.println(tree.rangeSum(2, 10));
        tree.put(9, "n9");
        System.out.println(tree.rangeSum(2, 10));

        BSTTreeImpl tree2 = buildByPreOrder(new int[]{4,2,1,3,6,5,7});
        tree2.printTree();
        BSTTreeImpl tree3 = buildByPreOrder2(new int[]{4,2,1,3,6,5,7});
        tree3.printTree();

        System.out.println(tree2.nearestShare(2,6)); // 4
        System.out.println(tree2.nearestShare(2,4)); // 4
        System.out.println(tree2.nearestShare(3,5)); // 4
        System.out.println(tree2.nearestShare(2,1)); // 2
        System.out.println(tree2.nearestShare(5,6)); // 6
        System.out.println(tree2.nearestShare(2,7)); // 4
        System.out.println(tree2.nearestShare(6,1)); // 4



    }

    /**
     *               4
     *            /     \
     *           2       6
     *         /   \   /   \
     *        1     3 5     7
     *
     */
    public static BSTTreeImpl createTree() {
        BSTNode n1 = new BSTNode(1, "n1");
        BSTNode n3 = new BSTNode(3, "n3");
        BSTNode n2 = new BSTNode(2, "n2", n1, n3);
        BSTNode n5 = new BSTNode(5, "n5");
        BSTNode n7 = new BSTNode(7, "n7");
        BSTNode n6 = new BSTNode(6, "n6", n5, n7);
        BSTNode n4 = new BSTNode(4, "n4", n2, n6);
        BSTTreeImpl tree = new BSTTreeImpl();
        tree.root = n4;
        return tree;
    }

    /**
     *               4
     *            /     \
     *           2       6
     *         /   \   /   \
     *        1     3 4     7
     * 构造一个无效二叉树
     */
    public static BSTTreeImpl createTree2() {
        BSTNode n1 = new BSTNode(1, "n1");
        BSTNode n3 = new BSTNode(3, "n3");
        BSTNode n2 = new BSTNode(2, "n2", n1, n3);
        BSTNode n5 = new BSTNode(4, "n5");
        BSTNode n7 = new BSTNode(7, "n7");
        BSTNode n6 = new BSTNode(6, "n6", n5, n7);
        BSTNode n4 = new BSTNode(4, "n4", n2, n6);
        BSTTreeImpl tree = new BSTTreeImpl();
        tree.root = n4;
        return tree;
    }

    public Object get(int key) {
        // return doGet(root, key);
        return doGet2(key);
    }
    // 递归实现
    public Object doGet(BSTNode n, int key) {
        if (n == null) return null;
        if (n.key == key) {
            return n.value;
        } else if (key < n.key) {
            return doGet(n.left, key);
        } else {
            return doGet(n.right, key);
        }
    }
    // 循环实现
    public Object doGet2(int key) {
        BSTNode n = root;
        while (true) {
            if (n == null) return null;
            if (n.key == key) {
                return key;
            } else if (key < n.key) {
                n = n.left;
            } else {
                n = n.right;
            }
        }
    }

    public Object min() {
        BSTNode n = root;
        if (n == null) return null;
        while (n.left != null) {
            n = n.left;
        }
        return n.value;
    }

    public Object max() {
        BSTNode n = root;
        if (n == null) return null;
        while (n.right != null) {
            n = n.right;
        }
        return n.value;
    }

    /**
     *                 10
     *              /     \
     *            5        20
     *          /   \     /   \
     *         3     8  12     27
     * 新增的节点只出现在在叶节点
     */
    public void put(int key, Object value) {
        if (root == null) root = new BSTNode(key, value);
        BSTNode n = root;
        while (true) {
            if (n.key == key) {
                n.value = value; // 找到，更新value
                break;
            }else if (key < n.key) {
                if (n.left == null) {
                    n.left = new BSTNode(key, value);
                    break;
                } else {
                    n = n.left;
                }
            } else {
                if (n.right == null) {
                    n.right = new BSTNode(key, value);
                    break;
                } else {
                    n = n.right;
                }
            }
        }
    }



    // 前驱，有左子树，则取左子树最大值；没有左子树，则取 该节点往上走的祖先节点路径中首个左侧祖先节点
    // ；否则，该key为最小，无前驱
    public Object predecessor(int key) {
        BSTNode leftParent = null; // 记录自左而来的祖先
        BSTNode d = root;
        while (true) {
            if (d == null) {
                System.out.println("没找到");
                return null;
            }
            if (key < d.key) {
                d = d.left;
            } else if (key > d.key) {
                leftParent = d;
                d = d.right;
            } else {
                System.out.println("找到了 " + d.value);
                if (d.left != null) { // 有左子树
                    d = d.left;
                    while (d != null) {
                        if (d.right != null) {
                            d = d.right;
                        }else {
                            return d.value;
                        }
                    }
                }else { // 无左子树，回溯寻找祖先节点中首个左侧节点
                    return leftParent == null ? null : leftParent.value;
                }
            }
        }

    }

    // 后继，同前驱类似，有右子树，则取右子树中最小值；无右子树，则回溯取祖先节点首个右侧节点
    public Object postdecessor(int key) {
        BSTNode node = doPostdecessor(key);
        return node == null ? null : node.value;
    }

    public BSTNode doPostdecessor(int key) {
        BSTNode rightParent = null; // 记录自右而来的祖先
        BSTNode d = root;
        while (true) {
            if (d == null) {
                System.out.println("没找到");
                return null;
            }
            if (key < d.key) {
                rightParent = d;
                d = d.left;
            } else if (key > d.key) {
                d = d.right;
            } else {
                System.out.println("找到了 " + d.value);
                if (d.right != null) { // 有右子树
                    d = d.right;
                    while (d != null) {
                        if (d.left != null) {
                            d = d.left;
                        }else {
                            return d;
                        }
                    }
                }else { // 无右子树，回溯寻找祖先节点中首个右侧节点
                    return rightParent;
                }
            }
        }
    }

    /**
     * 1.删除节点没有左孩子，将右孩子托孤给父节点；
     * 2.删除节点没有右孩子，将左孩子托孤给父节点；
     * 3.删除节点左右孩子都没有，已经被涵盖在情况1、情况2中，把null托孤给父节点；
     * 4.删除节点左右孩子都有，可以将它的后继结点（成为S）托孤给Parent，再称S的父亲为
     * SP，又分两种情况：
     *      1.SP就是被删除节点，此时D与S紧邻，只需将S托孤给Parent；
     *      2.SP不是被删除节点，此时D与S不相邻，此时需要将S的后代托孤给SP，再将S
     *      托孤给Parent。
     */
    public Object delete(int key) {
        BSTNode parent = null;
        BSTNode n = root;
        while (n != null) {
            if (key < n.key) {
                parent = n;
                n = n.left;
            } else if (key > n.key) {
                parent = n;
                n = n.right;
            } else {
                break;
            }
        }
        if (n == null) { // 未找到
            return null;
        }
        // 删除节点
        if (n.left == null) {
            shift(parent, n, n.right);
        }else if (n.right == null) {
            shift(parent, n, n.left);
        } else {
            // 查找delete后继，因为delete存在右子树，所以后继肯定在右子树中
            BSTNode d = n.right;
            BSTNode dp = null;
            while (d.left != null) {
                dp = d;
                d = d.left;
            }
            // 此时d为后继
            if (n.right == d) { // 相邻
                shift(parent, n, d);
                d.left = n.left;
            } else { // 不相邻
                shift(dp, d, d.right);
                shift(parent, n, d);
                d.left = n.left;
                d.right = n.right;
            }
        }
        return n.value;
    }

    // 托孤
    public void shift(BSTNode parent, BSTNode delete, BSTNode postdecessor) {
        if (parent == null) root = postdecessor;
        if (parent.left == delete) {
            parent.left = postdecessor;
        } else if (parent.right == delete) {
            parent.right = postdecessor;
        }
    }

    // 是否为有效二叉树，中序遍历，应该升序排列，如果某个节点比上一个节点小，说明无效
    public void isValid() {
        Stack<BSTNode> s = new Stack<>();
        BSTNode n = root;
        boolean hasPrev = false;
        int prev = 0;
        while (n != null || !s.isEmpty()) {
            if (n != null) {
                s.push(n);
                n = n.left;
            }else {
                BSTNode pop = s.pop();
                if (hasPrev) {
                    if(pop.key <= prev) {
                        System.out.println("无效");
                        break;
                    }
                }else {
                    hasPrev = true;
                }
                prev = pop.key;
                System.out.print(pop.value + " ");
                n = pop.right;
            }
        }
        System.out.println();
    }

    // 求范围和
    public int rangeSum(int low, int high) {
        return doRangeSum(root, low, high);
    }

    // 递归实现
    public int doRangeSum(BSTNode n, int low, int high) {
        if (n == null) return 0;
        if (n.key < low) {
            return doRangeSum(n.right, low, high);
        }
        if (n.key > high) {
            return doRangeSum(n.left, low, high);
        }
        return n.key + doRangeSum(n.left, low, high) + doRangeSum(n.right, low, high);
    }

    // 根据前序遍历结果还原二叉搜索树，遍历结果数组，依次插入元素
    public static BSTTreeImpl buildByPreOrder(int[] arr) {
        if (arr == null || arr.length == 0) return null;
        BSTNode root = new BSTNode(arr[0],arr[0]);
        for (int i = 1; i < arr.length; i++) {
            BSTNode n = root;
            while (n != null) {
                if (arr[i] < n.key) {
                    if (n.left == null) {
                        n.left = new BSTNode(arr[i],arr[i]);
                        break;
                    }else {
                        n = n.left;
                    }
                } else if (arr[i] > n.key) {
                    if (n.right == null) {
                        n.right = new BSTNode(arr[i],arr[i]);
                        break;
                    }else {
                        n = n.right;
                    }
                }else {
                    break;
                }
            }
        }
        BSTTreeImpl tree = new BSTTreeImpl();
        tree.root = root;
        return tree;
    }

    // 根据前序遍历结果还原二叉搜索树，分治法，递归
    // 4,2,1,3,6,5,7
    public static BSTTreeImpl buildByPreOrder2(int[] arr) {
        BSTNode root = doBuildByPreOrder2(arr, 0, arr.length-1);
        BSTTreeImpl tree = new BSTTreeImpl();
        tree.root = root;
        return tree;
    }

    // 递归方法
    public static BSTNode doBuildByPreOrder2(int[] arr, int begin, int end) {
        if (arr == null || end < begin) return null;
        BSTNode root = new BSTNode(arr[begin], arr[begin]);
        if (end == begin) return root;
        int k = begin+1;
        for (int i = begin+1; i <= end; i++) {
            if (arr[i] < arr[begin]) {
                k = i;
            } else {
                break;
            }
        }
        root.left = doBuildByPreOrder2(arr,begin+1, k);
        root.right = doBuildByPreOrder2(arr, k+1, end);
        return root;
    }


    /**
     * 查找两个节点的最近公共祖先
     *
     *                       --- 6 ---
     *                     /           \
     *                    2             8
     *                  /   \          / \
     *                 0     4        7   9
     *                     /   \
     *                    3     5
     * 规律：待查找节点 a b 在某节点两侧，那么该节点就是a和b的最近公共祖先
     */
    public int nearestShare(int a, int b) {
        BSTNode n = root;
        while (n != null) {
            if (a > n.key && b > n.key) {
                n = n.right;
            } else if(a < n.key && b < n.key) {
                n = n.left;
            } else if(a == n.key) {
                return a;
            } else if (b == n.key) {
                return b;
            } else {
                return n.key;
            }
        }
        return Integer.MIN_VALUE;
    }

    // 中序遍历打印树
    public void printTree() {
        Stack<BSTNode> s = new Stack<>();
        BSTNode n = root;
        while (n != null || !s.isEmpty()) {
            if (n != null) {
                s.push(n);
                n = n.left;
            } else {
                BSTNode pop = s.pop();
                System.out.print(pop.value + " ");
                n = pop.right;
            }
        }
        System.out.println();
    }

    static class BSTNode {
        int key;
        Object value;
        BSTNode left;
        BSTNode right;
        public BSTNode(int key) {
            this.key = key;
        }
        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }
        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}
